package hot100.logos1To10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author logos
 * date 2025/7/10 11:16
 * @version v1.0
 * @Package hot100
 */
public class logos9 {

    /**
     * 9.找到字符串中所有字母异位词
     * https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> ans = new ArrayList<>();
            char[] sArr = s.toCharArray();
            char[] pArr = p.toCharArray();
            int[] cnts = new int[26];
            int[] cntp = new int[26];
            for (int i = 0; i < pArr.length; i++) {
                cntp[pArr[i] - 'a']++;
            }
            for (int left = 0, right = 0; right < sArr.length; right++) {
                cnts[sArr[right] - 'a']++;
                if (right - left + 1 > pArr.length) {
                    cnts[sArr[left] - 'a']--;
                    left++;
                }
                if (Arrays.equals(cnts, cntp)) {
                    ans.add(left);
                }
            }
            return ans;
        }
    }
}
